package com.ljy.my_study.lintcode.二叉树的序列化和反序列化;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import com.ljy.my_study.leetcode.平衡二叉树.TestMain.TreeNode;

/**
 * @author James
 * @date 2018年9月19日
 */
public class TestMain {
	// 描述
	// 设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。
	//
	// 如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
	//
	// 对二进制树进行反序列化或序列化的方式没有限制，LintCode将您的serialize输出作为deserialize的输入，它不会检查序列化的结果。
	//
	// 您在真实的面试中是否遇到过这个题？
	// 样例
	// 给出一个测试数据样例， 二叉树{3,9,20,#,#,15,7}，表示如下的树结构：
	//
	// 3
	// / \
	// 9 20
	// / \
	// 15 7
	public static void main(String[] args) {
		TestMain testMain=new TestMain();
		TreeNode root=testMain.deserialize("1,#,2,#,#,3,#,#,#,#,#,4");
		testMain.serialize(root);
	}

	public String serialize(TreeNode root) {
		if(root==null) {
			return "";
		}
		
		List<Integer> arrList=new ArrayList<>(10);
		arrList.add(root.val);
		
		TreeNode thisNode=root;
		int count=0;
		setValToArr(arrList,thisNode,count);
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<arrList.size();i++) {
			if(arrList.get(i)==null) 
				sb.append("#,");
			else 
				sb.append(arrList.get(i)+",");
		}
		return sb.substring(0,sb.length()-1);
	}
	
	private void setValToArr(List<Integer> arrList,TreeNode thisNode,int count) {
		if(thisNode==null) {
			return;
		}
		if(arrList.size()<=count) {
			for(int i=0;i<=(arrList.size()/2);i++) {
				arrList.add(null);
			}
		}
		arrList.set(count, thisNode.val);
		
		int leftRootIndex=(count+1)*2-1;
		int rightRootIndex=(count+1)*2;
		setValToArr(arrList,thisNode.left,leftRootIndex);
		setValToArr(arrList,thisNode.right,rightRootIndex);
	}
	
	public TreeNode deserialize(String data) {
		if(data==null||data.isEmpty()) {
			return null;
		}
		String[] arrStr=data.split(",");
		TreeNode root=null;
		TreeNode[] treeNodeArr=new TreeNode[arrStr.length];
		for(int i=0;i<arrStr.length;i++) {
			if(!arrStr[i].equals("#")) {
				Integer intVal=Integer.valueOf(arrStr[i]);
				TreeNode thisNode=new TreeNode(intVal);
				if(i==0) {
					root=thisNode;
				}
				treeNodeArr[i]=thisNode;
				if(i%2==0) {
					if(i/2-1>=0) {
						if(treeNodeArr[i/2-1]!=null) {
							treeNodeArr[i/2-1].right=thisNode;
						}
					}
				}else {
					if((i+1)/2-1>=0) {
						if(treeNodeArr[(i+1)/2-1]!=null) {
							treeNodeArr[(i+1)/2-1].left=thisNode;
						}
					}
				}
			}
		}
		return root;
	}

	// Definition of TreeNode:
	public class TreeNode {
		public int val;
		public TreeNode left, right;

		public TreeNode(int val) {
			this.val = val;
			this.left = this.right = null;
		}

		@Override
		public String toString() {
			return "{\"val\":\"" + val + "\"} ";
		}
		
		
	}
}
